#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <sys/stat.h>
#include <fcntl.h>
#include <unistd.h>
#include <math.h>
#include "vectorssd_index.h"
#include "../min_list/min_list.h"
#include "point_set.h"
#include "../min_list/time_printer.h"
#include "bloomfilter.h"

#define ASSERT_NULL_POINTER(ptr, message) \
    do { \
        if ((ptr) == NULL) { \
            printf("[ERROR!]%s in %s is NULL\n", message, __func__); \
            exit(EXIT_FAILURE); \
        } \
    } while(0)


void print_DiskANN_index(INDEX_HEAD* head){
    printf("==============Loaded Index Head=================\n");

    printf("total_vectors:%lu\n",head->total_vectors);
    printf("dim:%lu\n",head->dim);
    printf("neighbor_count:%lu\n",head->neighbor_count);
    printf("bytes_per_dim:%lu\n",head->bytes_per_dim);
    printf("bytes_per_vector:%lu\n",head->bytes_per_vector);
    printf("vector_per_block:%lu\n",head->vector_per_block);
    printf("total_index_file_size:%lu\n",head->total_index_file_size);
    printf("block_size:%lu\n",head->block_size);
    printf("entry_count:%lu\n",head->entry_count);
    printf("entries_id:");
    for(int i=0; i<head->entry_count; i++)
        printf("%lu,",head->entries_id[i]);
    printf("\n");

    printf("================================================\n");
}

void destory_DiskANN_index(INDEX_HEAD* head){
    //free(head->entries_id);
}

//加载索引文件的头，不读取实际向量
//需要为每个数据集定制一个该函数，尽量把与数据集相关的字段修改都在这个函数里面完成
int load_index_file_SIFT1M(FILE *fp, INDEX_HEAD* head){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(head, "head");

    fseek(fp, 0, SEEK_SET);
    head->entry_count = 1;
    head->bytes_per_dim = 4; 
    head->block_size = 4096; //设置数据集的外部参数（无法从文件中读取到的）

    long tmp; //用来接收没用的字段
    fread(&tmp, 8, 1, fp);//0-7

    fread(&(head->total_vectors), 8, 1, fp); // 8-15
    fread(&(head->dim), 8, 1, fp);  //16-23
    //head->entries_id = (unsigned long*)malloc(sizeof(unsigned long)*(head->entry_count));
    fread(head->entries_id, 8, head->entry_count, fp);
    fread(&(head->bytes_per_vector), 8, 1, fp);
    fread(&(head->vector_per_block), 8, 1, fp);

    fread(&tmp, 8, 1, fp);
    fread(&tmp, 8, 1, fp);
    fread(&tmp, 8, 1, fp);
    fread(&(head->total_index_file_size), 8, 1, fp);

    //读取邻居数。我们假设每个节点的邻居数量是固定的
    fseek(fp, 4096+(head->dim)*(head->bytes_per_dim), SEEK_SET);
    fread(&(head->neighbor_count), 4, 1, fp);

    print_DiskANN_index(head);
    return 0;
}

int load_index_file_vectorssd(FILE *fp, INDEX_HEAD* head){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(head, "head");

    fseek(fp, 0, SEEK_SET);

    fread(head, sizeof(INDEX_HEAD), 1, fp);
    print_DiskANN_index(head);

    return 0;
}

//**********************加载数据集的相关函数**************************
VECTOR_FLOAT_ARRAY* create_vector_float_array(FILE *fp, int size){
    ASSERT_NULL_POINTER(fp, "fp");

    VECTOR_FLOAT_ARRAY* ret = malloc(sizeof(VECTOR_FLOAT_ARRAY));
    ret->size = size;

    //从文件中读取维数
    fseek(fp, 4, SEEK_SET);
    fread(&(ret->dim), 4, 1, fp);

    ret->features = malloc(size * sizeof(float) * ret->dim);

    return ret; 
}

int read_vector_float_array_fromfile(FILE *fp, int start_vector, int count, VECTOR_FLOAT_ARRAY* array){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(array, "array");

    int offset = 8 + start_vector*(array->dim)*sizeof(float);
    fseek(fp, offset, SEEK_SET);
    fread(array->features, sizeof(float)*(array->dim), count, fp);

    return 0;
}

float* get_vector_float(VECTOR_FLOAT_ARRAY* array, int index){
    return array->features+index*(array->dim);
}

void print_vector_float(float* vector, int dim){
    ASSERT_NULL_POINTER(vector, "vector");
    for(int i=0; i<dim; i++){
        printf("%.1f,",vector[i]);
    }
    printf("\n");
}

void destory_vector_float_array(VECTOR_FLOAT_ARRAY* buf){
    ASSERT_NULL_POINTER(buf, "buf");
    free(buf->features);
    free(buf);
}

//**********************加载groundtruth文件的相关函数**************************
GT_ARRAY* create_gt_array(FILE *fp, int k, int count){
    ASSERT_NULL_POINTER(fp, "fp");

    GT_ARRAY* ret = malloc(sizeof(GT_ARRAY));
    ret->k = k;
    ret->count = count;

    fseek(fp, 4, SEEK_SET);
    fread(&(ret->offset_factor), 4, 1, fp);
    ret->gts = malloc(ret->count * ret->offset_factor * 4);
    // printf("ret->k %d, ret->count %d, ret->offset_factor %u\n",ret->k,ret->count,ret->offset_factor);

    return ret;
}

int read_gt_array_fromfile(FILE *fp, int start_vector, int count, GT_ARRAY* array){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(array, "array");

    int offset = 8 + start_vector*(array->offset_factor)*4;
    fseek(fp, offset, SEEK_SET);
    fread(array->gts, array->offset_factor * 4, count, fp);

    return 0;
}

unsigned int* get_gt(GT_ARRAY* array, int index){
    ASSERT_NULL_POINTER(array, "array");

    return array->gts+index*array->offset_factor;
}

void print_gt_array(unsigned int* array, int k){
    ASSERT_NULL_POINTER(array, "array");

    for(int i=0; i<k; i++){
        printf("%u,",array[i]);
    }
    printf("\n");
}

void print_gt_array_cluster(unsigned int* array, int k, unsigned short* clusters){
    ASSERT_NULL_POINTER(array, "array");

    for(int i=0; i<k; i++){
        printf("%8u(%3u),",array[i],clusters[array[i]]);
    }
    printf("\n");
}

void destory_gt_array(GT_ARRAY* array){
    free(array->gts);
    free(array);
}

//**********************存储ANN检索结果的结构**************************
ANN_RESULT* create_ann_result(int k, int count){
    ANN_RESULT* ret=NULL;
    ret = malloc(sizeof(ANN_RESULT));
    memset(ret, 0, sizeof(ANN_RESULT));
    ret->k = k;
    ret->count = count;

    ret->ids = malloc(sizeof(unsigned int) * k * count);
    ret->distances = malloc(sizeof(float) * k * count);
    ret->flag = malloc(sizeof(int) * k * count);
    ret->iter_count = malloc(sizeof(int) * count);
    ret->recall = malloc(sizeof(float) * count);
    ret->io_count = malloc(sizeof(int) * count);
    ret->exclusion_count = malloc(sizeof(int) * count);
    ret->exclusion_list_count = malloc(sizeof(int) * count);

    return ret;
}

unsigned int* get_ann_result_ids(ANN_RESULT* result, int index){
    ASSERT_NULL_POINTER(result, "result");

    return result->ids + index*result->k;
}

float* get_ann_result_distances(ANN_RESULT* result, int index){
    ASSERT_NULL_POINTER(result, "result");

    return result->distances + index*result->k;
}

int* get_ann_result_flags(ANN_RESULT* result, int index){
    ASSERT_NULL_POINTER(result, "result");

    return result->flag + index*result->k;
}

unsigned* get_ann_result_iter(ANN_RESULT* result, int index){
    ASSERT_NULL_POINTER(result, "result");

    return result->iter_count + index;
}

float* get_ann_result_recall(ANN_RESULT* result, int index){
    ASSERT_NULL_POINTER(result, "result");

    return result->recall + index;
}

void print_ann_result(ANN_RESULT* result, int print_detail){
    ASSERT_NULL_POINTER(result, "result");

    unsigned int* ids;
    float* distances;
    int* flags;
    unsigned int* iter;
    float* recall;
    float total_recall=0.0; //用于计算召回率 
    unsigned int total_iter=0; //用于计算平均迭代次数
    unsigned int total_io_count=0; //用于计算平均迭代次数
    unsigned int total_exclusion_count=0;
    unsigned int total_exclusion_list_count=0;
    for(int i=0; i<result->count; i++){
        ids = get_ann_result_ids(result, i);
        distances = get_ann_result_distances(result, i);
        flags = get_ann_result_flags(result, i);
        iter = get_ann_result_iter(result, i);
        recall = get_ann_result_recall(result, i);
        total_recall += recall[0];
        total_iter += iter[0];
        total_io_count += result->io_count[i];
        total_exclusion_count += result->exclusion_count[i];
        total_exclusion_list_count += result->exclusion_list_count[i];

        if(!print_detail)
            continue;

        printf("[Result %d]---------------------------------------------------------------------------------------------------\n",i);
        printf("id        : ");
        for(int j=0; j<result->k; j++){
            printf("%8u, ",ids[j]);
        }
        printf("\ndistance  : ");
        for(int j=0; j<result->k; j++){
            printf("%8.2f, ",distances[j]);
        }
        printf("\nflag      : ");
        for(int j=0; j<result->k; j++){
            printf("0x%6X, ",flags[j]);
        }
        printf("\nI/O count : %8u, average %4.2f I/O per iter", result->io_count[i], (float)result->io_count[i]/iter[0]);
        printf("\niter      : %8u", iter[0]);
        printf("\nrecall    : %8.6f", recall[0]);
        printf("\nexclusion : %8u", result->exclusion_count[i]);
        printf("\nexclu list: %8u", result->exclusion_list_count[i]);
        printf("\n");
    }
    printf("[Summary]---------------------------------------------------------------------------------------------------\n");
    printf("Average I/O count :  %8.4f\n",(float)(total_io_count)/result->count);
    printf("Average recall    :    %8.6f\n",total_recall/result->count);
    printf("Average iter      : %8.3f\n",(float)total_iter/result->count);
    printf("Average exclusion : %8.3f\n",(float)total_exclusion_count/result->count);
    printf("Average exclu list: %8.3f\n",(float)total_exclusion_list_count/result->count);
    printf("Bloom error count : %8.6f\n",(float)result->bloom_error_count/result->total_check_visited_list_count);
}   

void destory_ann_result(ANN_RESULT* result){
    ASSERT_NULL_POINTER(result, "result");

    free(result->ids);
    free(result->distances);
    free(result->flag);
    free(result->iter_count);
    free(result->recall);
    free(result->io_count);
    free(result->exclusion_count);
    free(result->exclusion_list_count);
    free(result);
}

//**********************核心检索函数**************************
float l2_distance_float(float* A, float* B, int dim){
    float result = 0;
	float temp = 0;
	for(int i=0; i<dim; i++){
		temp = A[i]-B[i];
		temp = temp*temp;
		result += temp;
	}
	result = sqrt(result);
	return result;
}

int min(int a, int b){
    if(a>b)
        return b;
    return a;
}

//只负责一次迭代更新
//传入ANN_RESULT和result_offset是为了便于写入统计数据
int update_neighbor(FILE *fp, INDEX_HEAD* head, MINLIST* minlist, float* query, Point** visited_set, BloomFilter* bloom, ANN_RESULT* result, int result_offset, EXCLUSION_LIST* exclusion_list){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(head, "head");
    ASSERT_NULL_POINTER(minlist, "minlist");
    ASSERT_NULL_POINTER(query, "query");
    ASSERT_NULL_POINTER(visited_set, "visited_set");
    ASSERT_NULL_POINTER(bloom, "BloomFilter");
    ASSERT_NULL_POINTER(result, "result");
    ASSERT_NULL_POINTER(exclusion_list, "exclusion_list");

    //从头开始找首个没有访问过的节点
    for(int i=0; i<minlist->count; i++){ //对于查询向量的第i个邻居
        if(minlist->entries[i].flag & UNVISITED_FLAG == UNVISITED_FLAG){
            //置位
            minlist->entries[i].flag |= VISITED_FLAG;
            minlist->entries[i].flag &= ~UNVISITED_FLAG;
            //加入到已访问点集中
            add_point(visited_set, minlist->entries[i].id);
            bloom_add(bloom, minlist->entries[i].id);

            //读出该节点的邻居的id
            NODE_FLOAT* node_float_buf = create_node_float_buffer(head, VECTORSSD_FORMAT); //读取索引的缓冲区
            read_node_float_fromfile(fp, head, minlist->entries[i].id, node_float_buf); //第一次读，为了读邻居。这次IO通过后续的缓存优化避免

            //根据这些id找到这些邻居的原始向量
            MINLIST_ENTRY tmp_entry={0};
            NODE_FLOAT* neighbor_buf = create_node_float_buffer(head, VECTORSSD_FORMAT); //读取索引的缓冲区
            for(int n=0; n<head->neighbor_count; n++){ //对于第i个邻居的第n个邻居
                // printf("n%d:%u\n",n,node_float_buf->neighbors[n]);
                //首先判断该点是否访问过了，是的话就不用读了
                unsigned int neighbor_id = node_float_buf->neighbors[n];

                //仅用于测试，判断一下布隆过滤器的准确性.
                result->total_check_visited_list_count++;
                if(is_visited(*visited_set, neighbor_id)!=bloom_check(bloom, neighbor_id)){
                    //printf("Bloom filter error!\n");
                    result->bloom_error_count++;
                }

                if(VISITING_LIST_TYPE==UTHASH){
                    if(is_visited(*visited_set, neighbor_id)){
                        // printf("Point %u has visited\n",neighbor_id);
                        continue;
                    }
                }
                else if(VISITING_LIST_TYPE==BLOOMFILTER){
                    if(bloom_check(bloom, neighbor_id)){
                        continue;
                    }
                }

                //然后判断该点是否可以预先排除
                unsigned short cluster_id = node_float_buf->clusters[n];
                int is_exclusion = check_exclusion_list(exclusion_list, cluster_id);
                if(is_exclusion){ //返回1表示id可以排除，返回0表示无法排除
                    if(neighbor_id%100 >= READ_PROB){ //我们用节点id作为近似随机数，因为节点访问是随机的
                        // printf("cluster_id: %u is_exclusion: %d, Point %u can preliminary exclusion\n",cluster_id, is_exclusion, neighbor_id);
                        result->exclusion_count[result_offset]++;
                        continue;
                    }
                    else{
                        printf("although cluster_id: %u is_exclusion, we still read point %u\n",cluster_id,neighbor_id);
                    }
                }

                //然后读取第i个邻居的第n个邻居的原始向量用于计算距离
                //第二次读，这次读很难避免。
                read_node_float_fromfile(fp, head, neighbor_id, neighbor_buf);
                result->io_count[result_offset]++;

                //最后将这些邻居加入到minlist中
                tmp_entry.id = neighbor_id;
                tmp_entry.distance = l2_distance_float(neighbor_buf->features, query, head->dim);
                tmp_entry.flag = UNVISITED_FLAG;
                if(insert_minlist(minlist, &tmp_entry)>=0){ //insert_minlist返回非负数表明插入到了第几个位置，返回-1说明没有真的插入
                    update_exclusion_list(exclusion_list, minlist->entries[min(minlist->calculate_k, minlist->count)-1].distance); //更新预先排除表.这里没有考虑k和count不一致的情况
                }
            }
            destroy_node_float(node_float_buf);
            destroy_node_float(neighbor_buf);

            return 1; //也有可能没有更新，但是我们仍然返回1，在下一次迭代去判断
        }
    }
    return 0; //如果跳出for循环了，说明所有点都访问过了，不继续迭代了。
}

int vectorssd_disk_search(FILE *fp, INDEX_HEAD* head, VECTOR_FLOAT_ARRAY* query_array, int k, int calculate_k, ANN_RESULT* result, CLUSTER_INFO* cluster_info, FILE* debug_file){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(head, "head");
    ASSERT_NULL_POINTER(query_array, "query_array");
    ASSERT_NULL_POINTER(result, "result");
    ASSERT_NULL_POINTER(cluster_info, "cluster_info");

    if(query_array->size > result->count){
        printf("[vectorssd_disk_search]Error, result array(%d) smaller than query array(%d)\n",result->count,query_array->size);
        return -1;
    }
    int early_exclusion_count=0;
    for(int i=0; i<query_array->size; i++){ //对于每一个查询
        //开始检索这个查询向量。下面的代码是可并行的
        float* query = get_vector_float(query_array, i);
        // print_vector_float(query, query_array->dim);
        struct minlist* minlist = create_minlist(k); //创建最小数组，用于保存结果
        minlist->calculate_k = calculate_k;
        struct minlist_entry tmp_entry={0};
        NODE_FLOAT* node_float_buf = create_node_float_buffer(head, VECTORSSD_FORMAT); //创建读取索引的缓冲区
        Point* visited_set = NULL;  //使用uthash创建访问点集.
        BloomFilter bloom; //同时初始化bloom filter. 用于与uthash对比假阳性比例。
        bloom_init(&bloom);

        unsigned long start_t = get_time();
        EXCLUSION_LIST* exclusion_list = create_exclusion_list(cluster_info->count); //每个查询向量都需要一个排除列表
        early_exclusion_count += init_query(cluster_info, exclusion_list, minlist, query, fp, head);
        unsigned long init_done_t = get_time();
        // printf("[Query inited %d]\n", i);
        // print_minlist(minlist);
        // print_exclusion_list(exclusion_list, k);
        //1. 把入口点插入进来
        for(int j=0; j<head->entry_count; j++){ //对于每一个入口点
            tmp_entry.id = head->entries_id[j];
            read_node_float_fromfile(fp, head, tmp_entry.id, node_float_buf);
            // print_node_float(head, node_float_buf);
            // print_vector_float(query, head->dim);
            tmp_entry.distance = l2_distance_float(node_float_buf->features, query, head->dim);
            tmp_entry.flag |= UNVISITED_FLAG;
            // printf("0x%X\n",tmp_entry.flag);
            insert_minlist(minlist, &tmp_entry);
        }

        // 2.开始迭代更新minlist
        unsigned int* iter_count = get_ann_result_iter(result, i); //获取指针，直接在result结构中更新
        int is_continue = 1;
        unsigned long search_start_t = get_time();
        do{
            is_continue = update_neighbor(fp, head, minlist, query, &visited_set, &bloom, result, i, exclusion_list); //更新第i个查询
            iter_count[0]++;
            if(iter_count[0]>=ITER_LIMIT) //避免死循环无法收敛
                break;
        } while(is_continue);
        unsigned long search_done_t = get_time();
        unsigned long init_time = time_printer_elapsed(start_t, init_done_t);
        unsigned long search_time = time_printer_elapsed(search_start_t, search_done_t);
        char tmp[30];
        sprintf(tmp, "%d, %d, %2.2f, %lu, %lu\n",iter_count[0], result->io_count[i], (float)result->io_count[i]/iter_count[0], init_time, search_time);
        fwrite(tmp, 1, strlen(tmp), debug_file);

        //3.把minlits的结果写入result
        unsigned int* ids = get_ann_result_ids(result, i);
        float* distances = get_ann_result_distances(result, i);
        int* flags = get_ann_result_flags(result, i);
        for(int j=0; j<k; j++){
            ids[j] = minlist->entries[j].id;
            distances[j] = minlist->entries[j].distance;
            flags[j] = minlist->entries[j].flag;
        }
        result->exclusion_list_count[i] = exclusion_list_count(exclusion_list);

        //善后
        destory_minlist(minlist);
        destroy_node_float(node_float_buf);
        destory_exclusion_list(exclusion_list);
        free_set(visited_set);  // 释放集合内存
    }
    printf("Average early exclusion %d, ratio %4.2f%%\n",early_exclusion_count,(float)early_exclusion_count/cluster_info->count);

    return 0;
}

//**********************结果计算函数**************************
float calculate_recall(GT_ARRAY* gt_array, ANN_RESULT* ann_result, int k){
    ASSERT_NULL_POINTER(gt_array, "gt_array");
    ASSERT_NULL_POINTER(ann_result, "ann_result");

    if(gt_array->count != ann_result->count){
        printf("[calculate_recall]Error, length of gt_array and ann_result not match\n");
        return -1;
    }

    if(k > gt_array->k){
        printf("[calculate_recall]k larger than result length, set k from %d to %d\n",k,gt_array->count);
        k = gt_array->count;
    }

    float recall = 0.0;
    for(int i=0; i < gt_array->count; i++){ //对于向量i的检索结果
        unsigned int* gts = get_gt(gt_array, i);
        unsigned int* results = get_ann_result_ids(ann_result, i);
        float* result_recall = get_ann_result_recall(ann_result, i);

        int same = 0;
        int next_gt = 0;
        for(int j=0; j<k; j++){ //对于向量i的检索结果中的第j个近似向量
            while(next_gt < k){ 
                if(results[j]==gts[next_gt]){
                    same++;
                    next_gt++;
                    break;
                }
                next_gt++;
            }
            if(next_gt >= k){
                break;
            }
        }
        result_recall[0] = ((float)same)/k;
        recall += result_recall[0];
    }

    return recall/gt_array->count;
}

//**********************DiskANN的向量格式和处理函数**************************
//根据之前读取到的DiskANN_index信息，创建、初始化一个向量并返回
//可以创建针对不同索引文件类型的buffer
NODE_FLOAT* create_node_float_buffer(INDEX_HEAD* head, int format){
    ASSERT_NULL_POINTER(head, "head");

    NODE_FLOAT* ret = (NODE_FLOAT*)malloc(sizeof(NODE_FLOAT));
    ret->buf = malloc(head->bytes_per_vector);
    ret->features = ret->buf;

    if(format == DISKANN_FORMAT){
        ret->neighbors = (unsigned int*)((unsigned long)(ret->buf)+((head->bytes_per_dim)*(head->dim)+4));
        ret->clusters = NULL;
    }
    else if(format == VECTORSSD_FORMAT){
        ret->neighbors = (unsigned int*)((unsigned long)(ret->buf)+((head->bytes_per_dim)*(head->dim)));
        ret->clusters = (unsigned short*)((unsigned long)(ret->neighbors)+(head->neighbor_count)*4);
    }
    else{
        printf("[create_node_float_buffer]format error!\n");
        return NULL;
    }

    return ret;
}

//根据id从disk.index里面读取向量.buf的空间需要自己分配
//head需要首先通过load_index_file_SIFT1M读取
int read_node_float_fromfile(FILE *fp, INDEX_HEAD* head, unsigned int vid, NODE_FLOAT* vector){
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(head, "head");
    ASSERT_NULL_POINTER(vector, "vector");

    if(vid >= head->total_vectors){
        printf("[create_node_float_buffer]vid(%u) larger than total vector(%lu)!!\n",vid,head->total_vectors);
        return -1;
    }

    int block_number = vid/head->vector_per_block; //查找在第几个块。因为vid是从0开始的，所以直接除就可以了
    int offset = head->block_size + block_number*head->block_size; //偏移到所在块
    offset += (vid % head->vector_per_block)*head->bytes_per_vector; //块内偏移
    fseek(fp, offset, SEEK_SET);

    fread(vector->buf, head->bytes_per_vector, 1, fp);

    return 0;
}

void print_node_float(INDEX_HEAD* head, NODE_FLOAT* vector){
    ASSERT_NULL_POINTER(head, "head");
    ASSERT_NULL_POINTER(vector, "vector");

    printf("features:");
    for(int i=0; i<head->dim; i++){
        printf("%.0f, ",vector->features[i]);
    }

    printf("\nneighbors:");
    for(int i=0; i<head->neighbor_count; i++){
        printf("%u, ",vector->neighbors[i]);
    }
    printf("\n");

    if(vector->clusters != NULL){
        printf("clusters:");
        for(int i=0; i<head->neighbor_count; i++){
            printf("%u, ",vector->clusters[i]);
        }
        printf("\n");
    }
}

//销毁向量
void destroy_node_float(NODE_FLOAT* vector){
    free(vector->buf);
    free(vector);
}

//**********************VectorSSD优化部分**************************
//**************排除列表，用于记录某个向量检索时已排除的聚类*************
EXCLUSION_LIST* create_exclusion_list(int count){
    EXCLUSION_LIST* list = malloc(sizeof(EXCLUSION_LIST));
    memset(list, 0, sizeof(EXCLUSION_LIST));

    list->count = count;
    list->flag = malloc(count*sizeof(char));
    list->remain_distance = malloc(count*sizeof(float));

    memset(list->flag, 0, count*sizeof(char));
    memset(list->remain_distance, 0xFFFFFF, count*sizeof(float));

    return list;
}

void destory_exclusion_list(EXCLUSION_LIST* list){
    ASSERT_NULL_POINTER(list, "list");

    free(list->flag);
    free(list->remain_distance);
    free(list);
}

void print_exclusion_list(EXCLUSION_LIST* list, int limit){
    if(limit>list->count)
        limit = list->count;

    printf("flag: ");
    for(int i=0; i<limit; i++){
        printf("%6d, ",list->flag[i]);
    }

    printf("\ndist: ");
    for(int i=0; i<limit; i++){
        printf("%6.2f, ",list->remain_distance[i]);
    }
    printf("\n");
}

int update_exclusion_list(EXCLUSION_LIST* list, float cuteoff){
    ASSERT_NULL_POINTER(list, "list");

    int count = 0;
    for(int i=0; i<list->count; i++){
        if(list->flag[i] == 0){
            if(cuteoff < list->remain_distance[i]){
                list->flag[i] = 1;
                count++;
                // printf("cluster %d set excluded, cuteoff:%f remain_distance:%f\n",i,cuteoff, list->remain_distance[i]);
            }
        }
    }

    return count;
}

//返回1表示id可以排除，返回0表示无法排除
int check_exclusion_list(EXCLUSION_LIST* list, unsigned short cid){
    ASSERT_NULL_POINTER(list, "list");

    return list->flag[cid];
}

//返回有多少个排除了的
int exclusion_list_count(EXCLUSION_LIST* list){
    ASSERT_NULL_POINTER(list, "list");

    int count=0;
    for(int i=0;i<list->count;i++){
        if(list->flag[i])
            count++;
    }
    return count;
}

//************************从磁盘读取聚类信息*************************
unsigned int getFileSize(char *filename) {
    struct stat fileStat;

    // 打开文件
    int fileDescriptor = open(filename, O_RDONLY);
    if (fileDescriptor == -1) {
        perror("Failed to open file");
        return -1;
    }

    // 获取文件状态
    if (fstat(fileDescriptor, &fileStat) == -1) {
        perror("Failed to get file status");
        close(fileDescriptor);
        return -1;
    }

    // 关闭文件
    close(fileDescriptor);

    // 返回文件大小
    return (unsigned int)fileStat.st_size;
}

CLUSTER_INFO* create_load_cluster_info(char* centroid_path, char* centroid_info_path, int dim){
    CLUSTER_INFO* cluster_info = malloc(sizeof(CLUSTER_INFO));
    if(cluster_info == NULL){
        printf("[create_load_cluster_info]cluster_info malloc failed\n");
        exit(EXIT_FAILURE);
    } 
    memset(cluster_info, 0, sizeof(CLUSTER_INFO));

    int centroid_filesize = getFileSize(centroid_path);
    int centroid_info_filesize = getFileSize(centroid_info_path);
    // printf("centroid_filesize:%u centroid_info_filesize:%u\n",centroid_filesize,centroid_info_filesize);
    if(centroid_info_filesize%(sizeof(CLUSTER_INFO_ENTRY)) != 0){
        printf("[create_load_cluster_info]1.Size of %s error\n", centroid_info_path);
        exit(EXIT_FAILURE);
    }

    unsigned cluster_count = centroid_info_filesize/sizeof(CLUSTER_INFO_ENTRY);
    cluster_info->count = cluster_count;
    cluster_info->dim = dim;
    cluster_info->entries = malloc(centroid_info_filesize);
    if(cluster_info->entries == NULL){
        printf("[create_load_cluster_info]entries malloc failed\n");
        exit(EXIT_FAILURE);
    } 

    unsigned feature_size = cluster_count * cluster_info->dim * sizeof(float);
    cluster_info->centroid_feature = malloc(centroid_filesize); //存储的是中心点向量
    if(cluster_info->centroid_feature == NULL){
        printf("[create_load_cluster_info]centroid_feature malloc failed\n");
        exit(EXIT_FAILURE);
    } 

    //开始读取
    if(feature_size != centroid_filesize){
        printf("[create_load_cluster_info]2.Size of %s error\n", centroid_path);
        // exit(EXIT_FAILURE);
    }

    //读中心点向量
    FILE* centroid_fp = fopen(centroid_path, "rb");
    if(centroid_fp != NULL){
        fread(cluster_info->centroid_feature, centroid_filesize, 1, centroid_fp);
        fclose(centroid_fp);
    }

    //读中心点的信息
    int centroid_info_fd = open(centroid_info_path, O_RDONLY);
    if(centroid_info_fd != -1){
        read(centroid_info_fd, cluster_info->entries, centroid_info_filesize);
        close(centroid_info_fd);
    }

    // 打印看看
    printf("dim:%d, count:%d\n", cluster_info->dim, cluster_info->count);
    for(int i=0; i<cluster_info->count; i++){
        printf("[Cluster %d]\n",i);
        CLUSTER_INFO_ENTRY* entry = &(cluster_info->entries[i]);
        printf("near id:%d, far id:%d, near dist:%7.3f, far dist:%7.3f\n",entry->nearest_id, entry->farest_id, entry->nearest_distance, entry->farest_distance);
        printf("centroid: ");
        print_vector_float(cluster_info->centroid_feature+i*cluster_info->dim, 10);

        if(i>5){ //只打印前几个和最后一个
            i += cluster_info->count - 8;
        } 
    }

    return cluster_info;
}

float* get_centroid_feature(CLUSTER_INFO* cluster_info, int index){
    ASSERT_NULL_POINTER(cluster_info, "cluster_info");

    return cluster_info->centroid_feature + index * cluster_info->dim;
}

//根据聚类信息和查询点距离，填充exclusion_list的数据，并且将最近的聚类的中心点写入到min_list中。因此需要fp和head用于读取向量
int init_query(CLUSTER_INFO* cluster_info, EXCLUSION_LIST* exclusion_list, MINLIST* minlist, float* query, FILE* fp, INDEX_HEAD* head){
    ASSERT_NULL_POINTER(cluster_info, "cluster_info");
    ASSERT_NULL_POINTER(exclusion_list, "exclusion_list");
    ASSERT_NULL_POINTER(minlist, "minlist");
    ASSERT_NULL_POINTER(fp, "fp");
    ASSERT_NULL_POINTER(query, "query");
    ASSERT_NULL_POINTER(head, "head");

    NODE_FLOAT* nearest_node_buf = create_node_float_buffer(head, VECTORSSD_FORMAT); //读取索引的缓冲区
    MINLIST_ENTRY tmp_entry={0};
    for(int i=0; i<cluster_info->count; i++){ //对于每一个聚类
        //先根据聚类中心填充exclusion_list
        if(EXCULUSION_SWITCH){
            float* centroid = get_centroid_feature(cluster_info, i);
            exclusion_list->remain_distance[i] = l2_distance_float(centroid, query, cluster_info->dim);
            exclusion_list->remain_distance[i] -= REDUC_FACTOR*(cluster_info->entries[i].farest_distance);
        }

        //读取出最近的节点的原始向量
        if(CENTROID_ENTRY_SWITCH){
            unsigned int vid = cluster_info->entries[i].nearest_id;
            read_node_float_fromfile(fp, head, vid, nearest_node_buf);
            tmp_entry.id = vid;
            tmp_entry.distance = l2_distance_float(nearest_node_buf->features, query, head->dim);
            tmp_entry.flag = UNVISITED_FLAG;
            insert_minlist(minlist, &tmp_entry);
        }
    }
    int early_exclusion_count = update_exclusion_list(exclusion_list, minlist->entries[min(minlist->calculate_k, minlist->count)-1].distance);
    // printf("Early exclusion %d clusters\n",early_exclusion_count);

    return early_exclusion_count;
}

void destory_cluster_info(CLUSTER_INFO* cluster_info){
    free(cluster_info->entries);
    free(cluster_info->centroid_feature);
    free(cluster_info);
}